【⭐】CF 2121G

给定两个实数 $a$，$b$，如何在只使用初等代数运算的情况下求出 $a$ 与 $b$ 中的较大者 $max(a,b)$ 与较小者 $min(a,b)$？

提示一的答案：

设 $p_{l,r}$ 与 $q_{l,r}$ 分别代表子串 $s_l{s}_{l+1}\cdots s_r$ 中 $0$ 与 $1$ 的数目，依据提示二，有

因此将该二重求和拆开成两部分分别处理，对于前面的 ${\displaystyle \sum _{i=1}^n\sum _{j=i}^n(j-i+1)}$，可以令串长度 $l=j-i+1$ 从而将式子转化为 ${\displaystyle \sum _{l=1}^{n}l(n-l+1)}$ 从而在 $\mathcal{O}(n)$ 的时间复杂度内求出。或者还可以更进一步直接推出 ${\displaystyle \sum _{l=1}^{n}l(n-l+1)=\frac{n^3}{6}+\frac{n^2}{2}+\frac{n}{3}}$，具体推导过程由于不是本题解的重点此处不表。

重点在于处理后半部分，考虑维护前缀中 $0$ 多于 $1$ 的个数 $T_i=p_{1,i}-q_{1,i}$（特别的，$T_0=0$），则 $|p_{l,r}-q_{l,r}|=|T_r-T_{l-1}|$。考虑到二重求和覆盖到了所有的 $(i,j)$ 对，将 $T$ 由小到大排序以去掉求和式的绝对值，再交换求和顺序得到 ${\displaystyle \sum _{j=1}^n\sum _{i=1}^j{T}_j-T_{i-1}}$，考虑再维护一个 $T$ 的前缀和 $R$ 即可将式子化为 ${\displaystyle \sum _{j=1}^{n}j{T}_j-R_{j-1}}$，从而在 $\mathcal{O}(n)$ 的时间内解决此问题。注意不要忘了最终结果还要除 $2$。